
/*
 * University of Nebraska-Lincoln
 * 
 * Course: CSCE896 - AI and Heuristics in Software Engineering
 * Instructor: Dr. Myra Cohen
 * Project: Homework 2 - String Finder using Genetic Algorithm
 * Due: Oct 1, 2011
 * 
 * Author: ZhongYin Zhang
 * 
 * Description:
 * String Finder is a program to find the optimal (in this case known) solution
 * which is the string "AIandHeuristicSE" using Genetic Algorithm.
 * 
 * Genetic Algorithm Properties
 * - Initial Population = 32 chromosomes.
 * - Select 8 best chromosomes of each generation to be the parents.
 * - Crossover those parents (4 pairs) to generate 4 new children.
 *   Yield 16 chromosomes in every generation.
 * - Mutation Rate = 0.03 by default
 * - Four Fitness Modes [1 NEW]
 * - Three Crossover Modes [2 NEW]
 * - Incorporate Hill-Climb in crossover operation [NEW]
 * - Export population statistic to tab limit file. (for GA Mode only)
 * 
 * USAGE GENETIC: java StringGA <fitnessMode: (1,2,3)> <crossoverMode: (1,2,3)> <hillclimb: (integer)> <mutationRate:0.03 (double)> <varyMu%:0.0 (double)> [statFileName]
 * USAGE RANDOM : java StringGA <fitnessMode: (-1,-2,-3)> [statFileName]
 * (use StringGAverbose for running in verbose mode which will show all details of every GA operations)
 * 
 * fitnessMode:
 *   1 - ASCII Distance
 *  -1 - ASCII Distance [RANDOM]
 *   2 - Binary Decision
 *  -2 - Binary Decision [RANDOM]
 *   3 - Good Alleles Control [NEW]
 *  -3 - Good Alleles Control [RANDOM] [NEW]
 * crossoverMode:
 *   1 鈥�One-point crossover
 *   2 - Two-point crossover between any positions [NEW]
 *   3 - Two-point crossover between the same positions [NEW]
 * hillclimb (int): The number of trying to Crossover for better offspring using Hill-Climb approach (greater than 1 to activate crossover hill-climbing).
 * mutationRate (double): The percentage of genes in population space to be mutated.
 * varyMu% (double): The percentage of increasing mutation rate applied when the plateau was detected. [NEW] 
 * statFileName: a file for writing population statistic.
 * 
 * Language: Java Language
 * File List:
 * 1) StringGA.java
 *    This file contains five classes.
 *  - StringGA is the main program controlling all parameters and overall program.
 *  - GeneticAlgorithm is the major class for GA consisting of all genetic operator.
 *  - Chromosome is the class for storing chromosome and its fitness.
 *  - PopulationStat is the class to collect stat information.
 *  - MyUtil is the class consisting of other utility such as Random().
 * 2) StringGAverbose.java
 *    This is an idential main program, but in verbose mode. It also displays all
 * GA information during the operations. Note that there is only one class in this
 * source file, and can be compiled only after StringGA.java.
 * 
 * @author ZhongYin Zhang
 * @version StringGA.csce896.FALL2011  2011.10.01
 * 
 */

import java.util.*;
import java.io.*;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * StringGA is the main program controlling all parameters and overall program.
 * 
 * @author ZhongYin Zhang
 */
public class StringGA {

    /**
     * @param args the command line arguments
     */ 
    public static void main(String[] args) {
        int count = 0;
        int countLimit = 1000000;  // Limit number of generations
        int plaALL = 0;

        String paramPrint = new String();
        String usagePrint = new String();
            usagePrint += String.format("USAGE GENETIC: java StringGA <fitnessMode: (1,2,3)> <crossoverMode: (1,2,3)> <hillclimb: (integer)> <mutationRate:0.03 (double)> <varyMu%%:0.0 (double)> [statFileName]\n");
            usagePrint += String.format("USAGE RANDOM : java StringGA <fitnessMode: (-1,-2,-3)> [statFileName]\n");
            usagePrint += String.format("fitnessMode:\n");
            usagePrint += String.format("  1 - ASCII Distance\n");
            usagePrint += String.format(" -1 - ASCII Distance [RANDOM]\n");
            usagePrint += String.format("  2 - Binary Decision\n");
            usagePrint += String.format(" -2 - Binary Decision [RANDOM]\n");
            usagePrint += String.format("  3 - Good Alleles Control [NEW]\n");
            usagePrint += String.format(" -3 - Good Alleles Control [RANDOM] [NEW]\n");
            usagePrint += String.format("crossoverMode:\n");
            usagePrint += String.format("  1 - One-point crossover\n");
            usagePrint += String.format("  2 - Two-point crossover between any positions [NEW]\n");
            usagePrint += String.format("  3 - Two-point crossover between the same positions [NEW]\n");
            usagePrint += String.format("hillclimb (int): The number of trying to Crossover for better offspring using Hill-Climb approach\n");
            usagePrint += String.format("                  ( greater than 1 to activate Hill-Climb mode )\n");
            usagePrint += String.format("mutationRate (double): The percentage of genes in population space to be mutated\n");
            usagePrint += String.format("varyMu%% (double): The percentage of increasing mutation rate applied when the plateau was detected. [NEW] \n");
            usagePrint += String.format("statFileName: A file for writing population statistic\n");
        
        GeneticAlgorithm ga = new GeneticAlgorithm();
        Chromosome c = new Chromosome();
        
        boolean err = false;    // argument error checking. false is no error found.

        /**
         * Read all arguments
         */
        
        /**
         * Collecting parameters
         */
        if(args.length<=0)
            err = true;
        else
            ga.fitnessMode      = Integer.parseInt(args[0]);

        // GA MODE
        if(ga.fitnessMode>0){
            if(args.length>4){
                ga.crossoverMode        = Integer.parseInt(args[1]);
                ga.hillClimbCrossover   = Integer.parseInt(args[2]);
                ga.mutationRate         = Double.parseDouble(args[3]);
                ga.varyMuRate           = Double.parseDouble(args[4]);
                if(args.length>5)
                    ga.statFileName = args[5];
            }
            // If wrong number of arguments was found
            else
                err = true;
        }
        // RANDOM MODE
        else{
            if(args.length==2)
                ga.statFileName = args[1];
            else
                err = true;
            ga.crossoverMode = -1;      // no crossover, randomly pick new nChromosome/2 offsprings
            ga.hillClimbCrossover = 1;  // non hill-climb
            ga.mutationRate = 0.0;      // no mutation
        }
        
        if(err){
            System.out.println(usagePrint);
            System.exit(0);
        }        
        
        /**
         * Print all parameters
         */
        if(ga.fitnessMode<0)         // PURELY RANDOM MODE
            paramPrint += String.format("RANDOM MODE\n");

        paramPrint += String.format("Fitness Mode: ");;
        switch(Math.abs(ga.fitnessMode)){
            case 1: paramPrint += String.format("1 - ASCII Distance\n");
                    break;
            case 2: paramPrint += String.format("2 - Binary Decision\n");
                    break;
            case 3: paramPrint += String.format("3 - Good Alleles Control [NEW]\n");
                    break;
            default: err = true;
        }
        paramPrint += String.format("Crossover Rate: ");
        switch(ga.crossoverMode){
            case -1: paramPrint += String.format(" - RANDOM, without crossover\n");
                    break;
            case 1: paramPrint += String.format("1 - One-point crossover\n");
                    break;
            case 2: paramPrint += String.format("2 - Two-point crossover between any positions [NEW]\n");
                    break;
            case 3: paramPrint += String.format("3 - Two-point crossover between the same positions [NEW]\n");
                    break;
            default: err = true;
        }
        if(ga.hillClimbCrossover>1)
            paramPrint += String.format("Hill-Climb Limit: %d iterations per crossover. [NEW]\n", ga.hillClimbCrossover);
        paramPrint += String.format("Mutation Rate: %f\n", ga.mutationRate);
        if(ga.varyMuRate!=0)
            paramPrint += String.format("  increase %.1f%% mutation rate when plateau was detected. [NEW]\n", ga.varyMuRate*100);
        if(ga.statFileName!=null)
            paramPrint += String.format("Stat File: %s\n",ga.statFileName);
        paramPrint += String.format("\n");

        
        // If anything error, such as wrong parameter was found, then exit.
        if(err){
            System.out.println(usagePrint);
            System.exit(0);
        }else
            System.out.println(paramPrint);
        
        
        /**
         * Write Stat header file
         */
        if(ga.statFileName!=null){
            paramPrint += String.format("%s\t%s\t%s\t%s\t%s\t%s\t%s\n\n", "BEST","WORST","MEAN","SD","PLATEAU","GOOD_ALLE","BAD_ALLE");

            try {
                FileWriter fstream = new FileWriter(ga.statFileName);
//                FileWriter fstream = new FileWriter("/Volumes/IDATA/WORKSPACE/NetBeans/StringGA/"+ga.statFileName);
                BufferedWriter out = new BufferedWriter(fstream);
                out.write(paramPrint);
                out.close();
                fstream.close();
            } catch (IOException ex) {
        //            Logger.getLogger(GeneticAlgorithm.class.getName()).log(Level.SEVERE, null, ex);
                System.out.println("Write error !!!");
                System.exit(0);
            }         
        }
        
        
        
        /*************
         * Generate population until find the optimal solution or exceed iteration limit.
         */
        System.out.println(String.format("%-4s| %-16s | %-23s | %s | %-6s |%s| %s", "GEN","BEST CHROMOSOME","MATCH (#)", "AEHISacdeinrstu", "FITNESS", "DIST", "COMMENT"));
        ga.initPopulation(ga.nChromosome*2); // Doubling chromosomes twice only for the first gen.
        while(true){
            count++;

            c = ga.generate();  // select(); crossover(); mutate();
            plaALL += ga.pStat.plateau;

//            // Print progress
//            if(count%(countLimit/countLimit)==0 || c.getFitness()==0 || count==countLimit || count==1){
//                System.out.println(String.format("%4d| %s | %s | %7d | %.4f| %s",count, c.getChromosome(), ga.visualCorrect(c), ga.pStat.min, (ga.cntPlateau>=5?ga.mutationRate*1.1>1?1:ga.mutationRate*1.1:ga.mutationRate),(ga.cntPlateau>=5?"PLATEAU":"")));
//            }

            // Stopping Criteria
            if(c.getFitness()==0 || count==countLimit){
                if(count==countLimit)
                    System.out.println("Cannot find the solution!");
                else{
                    System.out.println(String.format("The solution was found in %d generations.", count));
                    System.out.println(String.format("Plateau detected: %d (%.1f%%) generations.", plaALL, (double)plaALL/count*100));
                    if(ga.hillClimbCrossover>1)
                        System.out.println("The number of iterations over hill-climb: "+ga.cntHill);
                }
                break;
            }
//            break;
        }
//        ga.printPopulation();
    }
}

/**
 * GeneticAlgorithm is the major class for GA consisting of all genetic operators.
 * 
 * @author ZhongYin Zhang
 */
class GeneticAlgorithm {
    ArrayList<Chromosome> population = new ArrayList<Chromosome>();     // List of chromosomes
    PopulationStat pStat  = new PopulationStat();                       // Current PopulationStat
    String  statFileName;                                               // Stat filename
//    final int   nInitPopulation   = 32; // Firstly initialize population.
    final int   nChromosome = 16;       // the population consists of 16 chromosomes
    final int   nGenes      = 16;       // 16 chromosome for each chromosome
    double      selectionRate = 0.5;    // Select best 50% of the population as parents for each generation.
    double      mutationRate  = 0.03;   // Randomly select (nChromosome*nGenes*0.03) chromosome to be changed
    int         fitnessMode   = 1;      // Fitness modes
    int         crossoverMode = 1;      // Crossover Mode
    int         hillClimbCrossover = 1; // The number of trying to Crossover
                                        // (HillClimb: crossover if better)
                                        // >1 to activate Hill-Climb mode
    double      varyMuRate = 0.0;       // Increase Mutation rate up for the specifying rate.
                                        // with 0.1 and original muRate=0.03, new muRate=0.03+(0.1*0.03)
    String      solution = "AIandHeuristicSE";  // String to be searched
    int         cntGen = 0;             // counter of the number of generation go so far
    int         cntHill = 0;            // counter of the number of iteration during hillclimb mode
    int         prevFitness;            // Best fitness of the prev generation
    int         cntPlateau = 0;         // If 4 consecutive gen have the same fitness,
                                        // increase 10% of the mutation rate of the 5th gen.
    boolean     verbose = false;        // Display all operations
    
    /**
     * Control all operation for each generation. It consists of Selection,
     * Crossover, and Mutation.
     * 
     * @return the best chromosome closest to the optimal solution (in this case,
     * the smallest fitness which is closest to ZERO).
     */
    public Chromosome generate(){
        int countLimit = 1000000;
        int plaInv  = 4;        // The number of allow walking on the same fitness before treated as PLATEAU
        String flag = new String(); // > < = of the fitness
        double r = this.mutationRate;
                
        this.cntGen++;
        
        /**
         * GA Operations
         */
        select(this.selectionRate);
        
        crossover(this.crossoverMode, this.hillClimbCrossover);
        
        // Mutate only in GA-MODE
        if(this.fitnessMode > 0){
            if(this.cntPlateau>=plaInv && this.varyMuRate!=0){
                r = this.mutationRate + (this.mutationRate*this.varyMuRate);
                if(r>1)
                    r = 1.0;
                mutate(r);
            }else
                mutate(this.mutationRate);
        }
        
        Chromosome best = Collections.min(this.population);
        
        // Plateau Detection
        if(this.cntGen==1){
            this.prevFitness = best.getFitness();
            flag = " ";
        }else{
            if(this.prevFitness==Collections.min(this.population).getFitness()){
                this.cntPlateau++;
                flag = "=";
            }else{
                this.cntPlateau = 0;
                if(this.prevFitness>Collections.min(this.population).getFitness())
                    flag = "<";
                else
                    flag = ">";
            }
            this.prevFitness = best.getFitness();
        }
        
        
        /*******************************
         * Calculate and Write STAT
         */
        this.pStat = this.calPopulationStat();
        
        // Mark Plateau flag in Stat.
        // Sum of this.pStat.plateau will show the number of generations on every plateaus
        if(this.cntPlateau==plaInv)
            this.pStat.plateau = plaInv+1;
        else if(this.cntPlateau>plaInv)
            this.pStat.plateau = 1;
        else
            this.pStat.plateau = 0;
                    
        if(this.statFileName!=null)
//            if(this.cntGen%(countLimit/500)==0 || best.getFitness()==0 || this.cntGen==countLimit || countLimit==1) // For RAMDOM MORE
                writePopulationStat(this.statFileName, this.pStat);
        
        // Print progress
        if(this.cntGen%(1)==0 || best.getFitness()==0 || this.cntGen==countLimit || countLimit==1){
            System.out.println(String.format("%4d| %s | %s | %s | %5d %s | %3d| %s"
                    ,this.cntGen, best.getChromosome(), visualCorrect(best), this.visualAlleles2(), best.getFitness(), flag, this.cntPlateau, (r>this.mutationRate?"+"+(int)(this.varyMuRate*100)+"%MU ":"")+(this.cntPlateau>plaInv?"- PLATEAU":"")));
        }
            
        return best;
    }
    
    /**
     * Selects parents for the next generation.
     * 
     * @param rate is the selection rate. It is 50% by default.
     */
    public void select(double rate){
        int nDel = (int)((1-rate)*population.size());
        
        // RANDOM MODE
        if(this.fitnessMode<0){
            for(int i=1;i<=nDel;i++)
                population.remove(0);
        }
        
        // GA MODE
        else{
            Collections.sort(population);

    //        System.out.println("After SORTING:");
    //        printPopulation();

            for(int i=1;i<=nDel;i++)
                population.remove(population.size()-1);
        }
        
        // Print SELECTION Details
        if(verbose){
            System.out.println("SELECTION ...");
            printPopulation();
        }
    }
    
    /**
     * Initializes the first population.
     * 
     * @param n is the number of chromosomes to be created.
     */
    public void initPopulation(int n) {
        for(int i=0;i<n;i++)
            this.population.add(getNewChromosome(this.nGenes));
//        printPopulation();
        select(0.5);          // Cut the half out to make it only 16 chromosomes
    }
    
    /**
     * Creates new chromosomes of 16 genes from alleles ['A'-'z'].
     * 
     * @param n the number of genes in a chromosome
     * @return new Chromosome
     */
    public Chromosome getNewChromosome(int n) {
        Chromosome c = new Chromosome();
        String genes = new String();
        
        for(int i=0;i<n;i++){
            genes += String.valueOf((char)MyUtil.randomRange('A', 'z'));
        }
        modifyChromosome(c, genes);
//        System.out.println("New chromosome: "+c);
        return c;
    }
    
    /**
     * Modifies genes in the chromosome and recalculate the fitness.
     * 
     * @param c is chromosome to be modified to have a newGenes.
     * @param newGenes will replace the old one.
     */
    public void modifyChromosome(Chromosome c, String newGenes) {
        c.setChromosome(newGenes);
        fitnessRecal(c, fitnessMode);
    }
        
    /**
     * Recalculates the fitness for the specifying chromosome.
     * 
     * @param c is chromosome to be recalculated the fitness.
     * @param mode is fitness function.
     */
    public void fitnessRecal(Chromosome c, int mode) {
        int m = Math.abs(mode);
        int f = 0;
        
        // Compare these two string
//        System.out.println(this.solution);
//        System.out.println(c.getChromosome());
        
        // First fitness: distance measure
        if(m==1){
            for(int i=0;i<c.getChromosome().length();i++){
                f += Math.pow(this.solution.codePointAt(i) - c.getChromosome().codePointAt(i), 2);
//                System.out.println("pow-2 of "+this.solution.codePointAt(i)+"-"+c.getChromosome().codePointAt(i)+" = "+Math.pow(this.solution.codePointAt(i) - c.getChromosome().codePointAt(i), 2)+" -sum-> "+f);
            }
        }
        
        // Second fitness: Matches 0, otherwise 1
        else if(m==2){
            for(int i=0;i<c.getChromosome().length();i++){
                f += (this.solution.codePointAt(i)==c.getChromosome().codePointAt(i))?0:1;
//                System.out.println("EQ? "+this.solution.codePointAt(i)+" vs "+c.getChromosome().codePointAt(i)+" = "+ ((this.solution.codePointAt(i)==c.getChromosome().codePointAt(i))?0:1) +" -sum-> "+f);
            }
        }
        
        // Third fitness: Match&&Contain -- Match?0:1 and ContainGoodGene?0:1
        else if(m==3){
            HashSet<String> cAlleles = new HashSet<String>();
            for(int i=0;i<c.getChromosome().length();i++){
                
                // Count the number of genes of this chromosome that not contains in the sulution
//                f += this.solution.contains(String.valueOf(c.getChromosome().charAt(i)))?0:1;
                
                // Count the number of genes of the solution that not contains in this chromosome
                f += c.getChromosome().contains(String.valueOf(this.solution.charAt(i)))?0:1;
                
                // Count incorrect genes, between the solution and this chromosome
                f += (this.solution.codePointAt(i)==c.getChromosome().codePointAt(i))?0:1;
                
//                cAlleles.add(String.valueOf(c.getChromosome().charAt(i)));
                
//                System.out.println("EQ? "+this.solution.codePointAt(i)+" vs "+c.getChromosome().codePointAt(i)+" = "+ ((this.solution.codePointAt(i)==c.getChromosome().codePointAt(i))?0:1) +" -sum-> "+f);
            }
            // Count bad alleles.
            // If 0, this chrom has the same degree of diversity.
            // In other word, this chrom contains all alleles that the solution has.
//            for(String a:cAlleles)
//                f += this.solution.contains(a)?0:1;
        }
        else
            f = 1;
        
        c.setFitness(f);
    }
    
    /**
     * Print all chromosomes in the population
     */
    public void printPopulation(){
        int i=0;
        for(Chromosome c : population)
            System.out.println((i++)+": "+ c);
        System.out.println("");
    }
    
    /**
     * Crossover EVEN and ODD pairs of selected parents.
     * 
     * @param mode is crossover method used.
     * @param hillclimb if greater than 1, hill-climb is activated.
     */
    public void crossover(int mode, int hillclimb) {
        int cut1=0;   // Cut position. Gene on this position is also contained in the cut.
        int cutLen=0; // Cut lenght
        int cut2=0;   // Cut position. Gene on this position is also contained in the cut.
        int flag;   // HC-parameter: 1 if the cut makes the better child.
        int cnt;    // HC-parameter: iteration counter
        
        ArrayList<Chromosome> newChild = new ArrayList<Chromosome>();
        
        /**
         * RANDOM MODE
         * : randomly generate (nChromosome/2) chromosomes as the new offsprings into population
         *   The number of remaining parents = (nChromosome/2)
         *   The number of new offsprings    = (nChromosome/2)
         *   Population size = nChromosome
         */
        if(mode<0){
            for(int i=1;i<=(nChromosome/2);i++)
                newChild.add(getNewChromosome(this.nGenes));
        }
            
        
        /**
         * GA MODE
         */
        else{
            if(verbose)
                System.out.println("CROSSOVER ...");

            // 0 1 2 3 4 5 6 7
            // |___| | |___| |
            //       |       |
            //   |___|   |___|

            // CrossOver the EVEN pairs (x=0), then ODD pairs (x=1).
            for(int x=0;x<=1;x++)
                for(int i=x;i+2<population.size();i+=4){
                    Chromosome c1 = new Chromosome();
                    Chromosome c2 = new Chromosome();
                    Chromosome o1 = new Chromosome();    // best pairs of offsprins found so far
                    Chromosome o2 = new Chromosome();
                    int ocut1=0;   // Cut position. Gene on this position is also contained in the cut.
                    int ocutLen=0; // Cut lenght
                    int ocut2=0;   // Cut position. Gene on this position is also contained in the cut.

                    String p1 = population.get(i).getChromosome();
                    String p2 = population.get(i+2).getChromosome();
                    cnt = 0;

                    do{
                        flag = 0;
                        cnt++;

                        /**
                         * One cut
                         */
                        if(mode==1){
                            // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
                            //   |_|_|_|_|_|_|_|_|__|__|__|__|__|__| Cutting positions 
                            cut1 = MyUtil.randomRange(1, nChromosome-1);

                            // Parent:
                            //      cutPoint
                            // |---A---|---B---|
                            // |---C---|---D---|
                            // ...
                            // Children:
                            // |---A---|---D---|
                            // |---C---|---B---|
                            modifyChromosome(c1, p1.substring(0, cut1) + p2.substring(cut1));
                            modifyChromosome(c2, p2.substring(0, cut1) + p1.substring(cut1));
                            
                        }

                        /**
                         * Two cuts on different sections
                         */
                        else if(mode==2){

                            // First cut of Parrent-1 (cut1)
                            //  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
                            // |_____________________________________________|    Cutting range 
                            //                   |     len=5   |
                            //                 cut1____________|
                            
                            cut1 = MyUtil.randomRange(0, nChromosome-1);
                            cutLen = MyUtil.randomRange(1, (nChromosome-1)-cut1+1);

                            // First cut of Parrent-2 (cut2)
                            //  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
                            // |_______________________________|##############    Cutting range 
                            //                            |     len=5   |
                            //                          cut2____________|
                            
                            cut2 = MyUtil.randomRange(0, (nChromosome-1)-cutLen+1);


                            // Parent:
                            //      cutPoint
                            // |--A--[--B--]--C--|
                            // |---X---[--Y--]-Z-|
                            // ...
                            // Children:
                            // |--A--[--Y--]--C--|
                            // |---X---[--B--]-Z-|
                            modifyChromosome(c1, p1.substring(0, cut1) + p2.substring(cut2,cut2+cutLen) + p1.substring(cut1+cutLen));
                            modifyChromosome(c2, p2.substring(0, cut2) + p1.substring(cut1,cut1+cutLen) + p2.substring(cut2+cutLen));

                        }

                        /**
                         * Two cuts on same sections
                         */
                        else if(mode==3){

                            // First cut of Parrent-1 (cut1)
                            //  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
                            // |_____________________________________________|    Cutting range 
                            //                   |     len=5   |
                            //                 cut1____________|

                            // First cut of Parrent-2 (cut1)
                            //  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
                            //                   |     len=5   |
                            //                 cut1____________|
                            
                            cut1 = MyUtil.randomRange(0, (nChromosome-1));
                            cutLen = MyUtil.randomRange(1, (nChromosome-1)-cut1+1);


                            // Parent:
                            //      cutPoint
                            // |--A--[--B--]--C--|
                            // |--X--[--Y--]--Z--|
                            // ...
                            // Children:
                            // |--A--[--Y--]--C--|
                            // |--X--[--B--]--Z--|
                            modifyChromosome(c1, p1.substring(0, cut1) + p2.substring(cut1,cut1+cutLen) + p1.substring(cut1+cutLen));
                            modifyChromosome(c2, p2.substring(0, cut1) + p1.substring(cut1,cut1+cutLen) + p2.substring(cut1+cutLen));

                        }
                        
                        if(hillclimb>1){
                            // If some offsprings is better than their parents, pick them.
                            if( (c1.getFitness() < population.get(i).getFitness() && c1.getFitness() < population.get(i+2).getFitness() ) ||
                                (c2.getFitness() < population.get(i).getFitness() && c2.getFitness() < population.get(i+2).getFitness() )
                              ){
                                flag = 1; // Mimic Hill-Climb : crossover only if better offspring was found
                            
                            // Else if this is the first time OR c1 or c2 better than their best found so far,
                            // Then, temporary keep two offsprings.
                            }else if( (c1.getFitness() < o1.getFitness() && c1.getFitness() < o2.getFitness() ) ||
                                    (c2.getFitness() < o1.getFitness() && c2.getFitness() < o2.getFitness() ) ||
                                    (cnt==1)
                                    ){
                                    o1 = c1;
                                    o2 = c2;
                                    ocut1 = cut1;
                                    ocut2 = cut2;
                                    ocutLen = cutLen;
                            // for the last iteration, if no offspring better than their parents, select the best offspring found so far
                            }else if(cnt==hillclimb){
                                c1 = o1;
                                c2 = o2;
                                cut1 = ocut1;
                                cut2 = ocut2;
                                cutLen = ocutLen;
                            }
                        }

                    }while( flag!=1 && cnt<hillclimb ); //-- HC-Feature
                    this.cntHill += cnt;

                    // Add two new children
                    newChild.add(c1);
                    newChild.add(c2);
                    
                    
                    // Print Crossover Details
                    if(verbose){
                        switch(mode){
                            case 1: 
                                System.out.println("Mating "+i+" and "+(i+2)+" at "+cut1);
                                System.out.print("Parents : ");
                                System.out.print(p1.substring(0,cut1)+" | "+p1.substring(cut1));
                                System.out.println("  X  "+p2.substring(0,cut1)+" | "+p2.substring(cut1));
                                System.out.print("Children: ");
                                System.out.print(c1.getChromosome().substring(0,cut1)+" | "+c1.getChromosome().substring(cut1));
                                System.out.println("     "+c2.getChromosome().substring(0,cut1)+" | "+c2.getChromosome().substring(cut1));
                                break;
                            case 2:
                                System.out.println("Mating "+i+" and "+(i+2)+" at "+cut1+" and "+cut2+" of length "+cutLen);
                                System.out.print("Parents : ");
                                System.out.print(String.format("%s [ %s ] %s", p1.substring(0, cut1), p1.substring(cut1,cut1+cutLen), p1.substring(cut1+cutLen)));
                                System.out.println(String.format("  X  %s [ %s ] %s", p2.substring(0, cut2), p2.substring(cut2,cut2+cutLen), p2.substring(cut2+cutLen)));
                                System.out.print("Children: ");
                                System.out.print(String.format("%s [ %s ] %s", c1.getChromosome().substring(0, cut1), c1.getChromosome().substring(cut1,cut1+cutLen), c1.getChromosome().substring(cut1+cutLen)));
                                System.out.println(String.format("     %s [ %s ] %s", c2.getChromosome().substring(0, cut2), c2.getChromosome().substring(cut2,cut2+cutLen), c2.getChromosome().substring(cut2+cutLen)));
                                break;
                            case 3:
                                System.out.println("Mating "+i+" and "+(i+2)+" at "+cut1+" of length "+cutLen);
                                System.out.print("Parents : ");
                                System.out.print(String.format("%s [ %s ] %s", p1.substring(0, cut1), p1.substring(cut1,cut1+cutLen), p1.substring(cut1+cutLen)));
                                System.out.println(String.format("  X  %s [ %s ] %s", p2.substring(0, cut1), p2.substring(cut1,cut1+cutLen), p2.substring(cut1+cutLen)));
                                System.out.print("Children: ");
                                System.out.print(String.format("%s [ %s ] %s", c1.getChromosome().substring(0, cut1), c1.getChromosome().substring(cut1,cut1+cutLen), c1.getChromosome().substring(cut1+cutLen)));
                                System.out.println(String.format("     %s [ %s ] %s", c2.getChromosome().substring(0, cut1), c2.getChromosome().substring(cut1,cut1+cutLen), c2.getChromosome().substring(cut1+cutLen)));
                                break;
                            default:
                        }
                    }
                    
                }
        }
        
        this.population.addAll(newChild);
        
//        System.out.println("After CROSSOVER:");
//        printPopulation();
    }
    
    /**
     * Mutates the population according to the specified mutation rate.
     * 
     * @param rate is the mutation rate. The number of genes to be mutated equal
     * to (int)(nChromosome*nGenes*rate).
     */
    public void mutate (double rate) {
        
        /**
         * Random space in (0 to (nChromosome*nGenes)-1)
         *  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
         * 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
         * .
         * .
         * .
         * 241.........................................255
         */
        int mutatePoint;    // Randomly pick gene in the population space
        int atChrom;        // Chromosome being to mutate
        int atGene;         // Gene of the chromosome being to mutate
        char mutant;        // Mutant gene being to replace the original gene.
        
        // Calculate the number of genes to be mutated.
        int nMutate = (int)Math.ceil(nChromosome*nGenes*rate);
        
        if(verbose)
            System.out.println(String.format("\nMUTATION (%.2f) ...", rate));
        
        for(int i=1;i<=nMutate;i++){
            mutatePoint = MyUtil.randomRange(0, (nChromosome*nGenes)-1);
            atChrom = (int)(mutatePoint / nChromosome);
            atGene  = (int)(mutatePoint % nChromosome);
            mutant  = (char)MyUtil.randomRange('A', 'z');
            String oldChrom = population.get(atChrom).getChromosome();
            
            modifyChromosome(population.get(atChrom), oldChrom.substring(0,atGene)+mutant+oldChrom.substring(atGene+1));
            
            if(verbose){
                System.out.print(String.format("Mutate: mutant=%s at %3d #Chrom%2d #Gene%2d", mutant, mutatePoint, atChrom, atGene));
                System.out.print("   "+oldChrom.substring(0,atGene)+" "+oldChrom.charAt(atGene) +" "+oldChrom.substring(atGene+1));
                System.out.println(" --> "+oldChrom.substring(0,atGene)+" "+mutant+" "+oldChrom.substring(atGene+1));
            }
        }
        
        if(verbose){
            System.out.println("After MUTATION:");
            printPopulation();
        }
        
    }
    
    
    /**
     * Writes stat info to file. The stat consists of min, max, mean, and sd. of 
     * fitness in the population for each generation.
     * 
     * @param fstat is the file to be written.
     */
    public void writePopulationStat(String fstat, PopulationStat stat) {
        
        String wrt = String.format("%d\t%d\t%.2f\t%.2f\t%d\t%d\t%d\n", stat.min,stat.max,stat.mean,stat.sd,stat.plateau,stat.goodAllele.size(),stat.badAllele.size());

        try {
            FileWriter fstream = new FileWriter(fstat, true);
//            FileWriter fstream = new FileWriter("/Volumes/IDATA/WORKSPACE/NetBeans/StringGA/"+fstat, true);
            BufferedWriter out = new BufferedWriter(fstream);
            out.write(wrt);
            out.close();
            fstream.close();
        } catch (IOException ex) {
//            Logger.getLogger(GeneticAlgorithm.class.getName()).log(Level.SEVERE, null, ex);
            System.out.println("Write error !!!");
            System.exit(0);
        }
    }

    /**
     * Recalculates population stat.
     * 
     * @return population stat.
     */
    public PopulationStat calPopulationStat() {
        int     sum = 0;
        double  dif = 0;
        int     f;

        PopulationStat stat = new PopulationStat();
        
        // Finding MAX and MIN
        for(Chromosome c : population){
            f = c.getFitness();
            if(stat.max<f || stat.max==-1)
                stat.max = f;
            if(stat.min>f || stat.min==-1)
                stat.min = f;
            sum += f;
            
            for(int i=0;i<c.getChromosome().length();i++){
                if(this.solution.contains(String.valueOf(c.getChromosome().charAt(i)))){
                    stat.goodAllele.add(String.valueOf(c.getChromosome().charAt(i)));
                }else
                    stat.badAllele.add(String.valueOf(c.getChromosome().charAt(i)));
            }
            
        }
        // Calculate average
        stat.mean = sum/population.size();
        
        // Finding Standard Deviation
        for(Chromosome c : population){
            f = c.getFitness();
            dif += Math.pow(stat.mean - f, 2);
        }
        stat.sd = Math.sqrt(dif/population.size());
                
//        System.out.println(stat);
        return stat;
    }
    
    public String visualCorrect(Chromosome c) {
        String s = new String();
        int cnt = 0;
        for(int i=0;i<c.getChromosome().length();i++){
            if(this.solution.codePointAt(i)==c.getChromosome().codePointAt(i)){
                s += "#";
                cnt++;
            }else
                s += "?";
        }
        s += String.format(" %5.1f%%", (double)cnt/c.getChromosome().length()*100);
        return s;
    }
    
    public String visualAlleles() {
        String s = new String();
        
        for(String a : this.pStat.goodAllele)
            s += a;
        s += "|";
        for(String a : this.pStat.badAllele)
            s += a;
        
        return s;
    }
    
    public String visualAlleles2() {
        String solAlleles = "AEHISacdeinrstu";
        String s = new String();
        
        for(int i=0;i<solAlleles.length();i++){
            s += (this.pStat.goodAllele.contains(String.valueOf(solAlleles.charAt(i))))?"1":"0";
        }
        
        return s;
    }
}

/**
 * PopulationStat is the class to collect stat information.
 * 
 * @author ZhongYin Zhang
 */
class PopulationStat {
    int     min = -1;
    int     max = -1;
    double  mean;
    double  sd;
    int     plateau = 0;
    TreeSet<String> goodAllele = new TreeSet<String>();
    TreeSet<String> badAllele = new TreeSet<String>();

    @Override
    public String toString(){
        return String.format("Best: %d  Worst: %d  Mean: %.2f  SD.: %.2f", min, max, mean, sd);
    }
}

/**
 * Chromosome is the class for storing chromosome and its fitness.
 * 
 * @author ZhongYin Zhang
 */
class Chromosome implements Comparable<Chromosome>{
    private String  chromosome = "";
    private int fitness;

    @Override
    public int compareTo(Chromosome t) {
//        throw new UnsupportedOperationException("Not supported yet.");
        return this.getFitness() - t.getFitness();    // asc order
    }

    @Override
    public String toString(){
        return this.getChromosome()+" ("+this.getFitness()+")";
    }

    /**
     * @return the chromosome
     */
    public String getChromosome() {
        return chromosome;
    }

    /**
     * @param chromosome the chromosome to set
     */
    public void setChromosome(String chromosome) {
        this.chromosome = chromosome;
    }

    /**
     * @return the fitness
     */
    public int getFitness() {
        return fitness;
    }

    /**
     * @param fitness the fitness to set
     */
    public void setFitness(int fitness) {
        this.fitness = fitness;
    }
} 

/**
 * MyUtil is the class consisting of other utility such as Random().
 * 
 * @author ZhongYin Zhang
 */
class MyUtil {
    public static int randomRange(int Min, int Max){
        return Min + (int)(Math.random() * ((Max - Min) + 1));
    }    
}